package com.wtgroup.demo.leetcode.q147_链表进行插入排序;

import com.wtgroup.demo.common.bean.LinkNode;

/**
 * @author dafei
 * @version 0.1
 * @date 2021/4/16 12:28
 */
public class Q147_LC {
    public static void main(String[] args) {
        int[][] inputs = {
                {4, 2, 1, 3},
                {-1, 5, 3, 4, 0},
                {1},
                {4,2,1,3},
        };
        Q147_LC exe = new Q147_LC();
        for (int[] input : inputs) {
            LinkNode head = LinkNode.toListNode(input);
            LinkNode linkNode = exe.insertionSortList(head);
            LinkNode.print(linkNode);
        }
    }

    /**
     * [技巧] 搞一个 dummyHead 节点, 方便很多
     * [答案]
     */

    public LinkNode insertionSortList(LinkNode head) {
        if (head==null) {
            return head;
        }

        LinkNode dummyHead = new LinkNode();
        dummyHead.next = head;
        LinkNode lastSorted = head;
        LinkNode cur = null;
        while ((cur = lastSorted.next) != null) {
            if(lastSorted.value <=cur.value) {
                // 就在尾结点后面, 后移 "分界点" 就可以了
                lastSorted = cur;
                // cur = lastSorted.next;
            } else {
                LinkNode pre = dummyHead;
                while (pre.next.value <= cur.value) { // 由于上面已经判断了 lastSorted 和 cur , 这里必定在不越界的条件下, 退出循环
                    pre = pre.next;
                }
                lastSorted.next = cur.next;
                cur.next = pre.next;
                pre.next = cur;
            }
        }

        return dummyHead.next;
    }


}
